class LruEntry<K, V> {
  next: LruEntry<K, V> | null
  prev: LruEntry<K, V> | null
  key: K | null
  value: V | null

  constructor(k?: K, v?: V) {
    this.next = null
    this.prev = null
    this.key = k || null
    this.value = v || null
  }
}

class LruCache<K, V> {
  map: Map<K, LruEntry<K, V>>
  cap: number
  head: LruEntry<K, V>
  tail: LruEntry<K, V>

  constructor(cap: number) {
    this.cap = cap
    this.map = new Map()
    this.head = new LruEntry<K, V>()
    this.tail = new LruEntry<K, V>()

    this.head!.next = this.tail
    this.tail!.prev = this.head
  }

  get len(): number {
    return this.map.size
  }
  
  put(k: K, v: V): V | null {
    if (this.map.has(k)) {
      let node = this.map.get(k)!
      this.detach(node)
      this.attach(node)
      const oldv = node.value
      node.value = v
      return oldv
    } else {
      if (this.cap == 0) {
        return null
      }

      if(this.len == this.cap) {
        let old_key = this.tail.prev!.key!
        let old_node = this.map.get(old_key)!
        this.map.delete(old_key)
        this.detach(old_node)
      }

      let node = new LruEntry(k, v)
      this.map.set(k, node)
      this.attach(node)
      return null
    }
  }

  get(k: K): V | null {
    if (this.map.has(k)) {
      let node = this.map.get(k)!
      this.detach(node)
      this.attach(node)
      return node.value
    } else {
      return null
    }
  }

  detach(node: LruEntry<K, V>) {
    node.prev!.next = node.next
    node.next!.prev = node.prev
  }

  attach(node: LruEntry<K, V>) {
    node.next = this.head.next
    node.prev = this.head
    this.head.next = node
    node.next!.prev = node
  }
}

const cache = new LruCache(2)
cache.put('apple', 3)
cache.put('banana', 2)

console.assert(cache.get('apple') === 3, 'get apple')
console.assert(cache.get('banana') === 2, 'get banana')
console.assert(cache.get('pear') === null, 'get pear')

console.assert(cache.put('banana', 4) === 2, 'put banana')
console.assert(cache.put('pear', 5) === null, 'put pear')

console.assert(cache.get('pear') === 5, 'get pear 2')
console.assert(cache.get('banana') === 4, 'get banana 2')
console.assert(cache.get('apple') === null, 'get apple 2')

